『Algebra, Topology, Differential Calculus, and Optimization Theory For Computer Science and Machine Learning』 目次
2. 群論、環、体(Groups, Rings, and Fields) 21 I 線形代数(Linear Algebra) 47 4. 距離と線形写像(Matrices and Linear Maps)
9. ベクトルノルムと行列ノルム
10. 線形システムを解く反復法(?)
Iterative Methods for Solving Linear Systems
13. 任意行列のQR分解(QR-Decomposition for Arbitrary Matrices)
14. ハミルトニアン空間(Hermitian Spaces)
16. 単位 SO(3)の四元数および回転(Unit Quaternions and Rotations in SO(3) ) 19. 有限要素法入門(Introduction to The Finite Elements Method) 20. グラフとグラフラプラシアン；基本事項
II アフィン幾何学と射影幾何学(Affine and Projective Geometry)
24 基本的なアフィン幾何学(Basics of Affine Geometry)
25. アフィン空間のベクトル空間への埋め込み(Embedding an Affine Space in a Vector Space) V トポロジー, 微分積分 1309
37 トポロジー 1311
38 フラクタルについての寄り道(A Detour On Fractals) 1391
39 微分積分(Differential Calculus) 1399
VIII 非線形最適化
1 Introduction 19
2 Groups, Rings, and Fields 21
2.1 Groups, Subgroups, Cosets . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2 Cyclic Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.3 Rings and Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
I Linear Algebra 47
3 Vector Spaces, Bases, Linear Maps 49
3.1 Motivations: Linear Combinations, Linear Independence, Rank . . . . . . . 49
3.2 Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.3 Indexed Families; the Sum Notation ∑i∈I ai . . . . . . . . . . . . . . . . . . 64
3.4 Linear Independence, Subspaces . . . . . . . . . . . . . . . . . . . . . . . . 70
3.5 Bases of a Vector Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.6 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3.7 Linear Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.8 Quotient Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
3.9 Linear Forms and the Dual Space . . . . . . . . . . . . . . . . . . . . . . . . 98
3.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
3.11 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
4 Matrices and Linear Maps 111
4.1 Representation of Linear Maps by Matrices . . . . . . . . . . . . . . . . . . 111
4.2 Composition of Linear Maps and Matrix Multiplication . . . . . . . . . . . 116
4.3 Change of Basis Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
4.4 The Effect of a Change of Bases on Matrices . . . . . . . . . . . . . . . . . 125
4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
4.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
5 Haar Bases, Haar Wavelets, Hadamard Matrices 137
5.1 Introduction to Signal Compression Using Haar Wavelets . . . . . . . . . . 137
5.2 Haar Matrices, Scaling Properties of Haar Wavelets . . . . . . . . . . . . . . 139
5.3 Kronecker Product Construction of Haar Matrices . . . . . . . . . . . . . . 144
5.4 Multiresolution Signal Analysis with Haar Bases . . . . . . . . . . . . . . . 146
5.5 Haar Transform for Digital Images . . . . . . . . . . . . . . . . . . . . . . . 149
5.6 Hadamard Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
5.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
5.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
6 Direct Sums 163
6.1 Sums, Direct Sums, Direct Products . . . . . . . . . . . . . . . . . . . . . . 163
6.2 Matrices of Linear Maps and Multiplication by Blocks . . . . . . . . . . . . 173
6.3 The Rank-Nullity Theorem; Grassmann’s Relation . . . . . . . . . . . . . . 186
6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
6.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
7 Determinants 201
7.1 Permutations, Signature of a Permutation . . . . . . . . . . . . . . . . . . . 201
7.2 Alternating Multilinear Maps . . . . . . . . . . . . . . . . . . . . . . . . . . 205
7.3 Definition of a Determinant . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
7.4 Inverse Matrices and Determinants . . . . . . . . . . . . . . . . . . . . . . . 218
7.5 Systems of Linear Equations and Determinants . . . . . . . . . . . . . . . . 221
7.6 Determinant of a Linear Map . . . . . . . . . . . . . . . . . . . . . . . . . . 223
7.7 The Cayley–Hamilton Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 224
7.8 Permanents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
7.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
7.10 Further Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
7.11 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
8 Gaussian Elimination, LU, Cholesky, Echelon Form 239
8.1 Motivating Example: Curve Interpolation . . . . . . . . . . . . . . . . . . . 239
8.2 Gaussian Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
8.3 Elementary Matrices and Row Operations . . . . . . . . . . . . . . . . . . . 248
8.4 LU -Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
8.5 P A = LU Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
8.6 Proof of Theorem 8.5 ~ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
8.7 Dealing with Roundoff Errors; Pivoting Strategies . . . . . . . . . . . . . . . 270
8.8 Gaussian Elimination of Tridiagonal Matrices . . . . . . . . . . . . . . . . . 272
8.9 SPD Matrices and the Cholesky Decomposition . . . . . . . . . . . . . . . . 274
8.10 Reduced Row Echelon Form . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
8.11 RREF, Free Variables, Homogeneous Systems . . . . . . . . . . . . . . . . . 289
8.12 Uniqueness of RREF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
8.13 Solving Linear Systems Using RREF . . . . . . . . . . . . . . . . . . . . . . 294
8.14 Elementary Matrices and Columns Operations . . . . . . . . . . . . . . . . 300
8.15 Transvections and Dilatations ~ . . . . . . . . . . . . . . . . . . . . . . . . 301
8.16 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
8.17 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
9 Vector Norms and Matrix Norms 319
9.1 Normed Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
9.2 Matrix Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
9.3 Subordinate Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336
9.4 Inequalities Involving Subordinate Norms . . . . . . . . . . . . . . . . . . . 343
9.5 Condition Numbers of Matrices . . . . . . . . . . . . . . . . . . . . . . . . . 345
9.6 An Application of Norms: Inconsistent Linear Systems . . . . . . . . . . . . 354
9.7 Limits of Sequences and Series . . . . . . . . . . . . . . . . . . . . . . . . . 355
9.8 The Matrix Exponential . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
9.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
9.10 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363
10 Iterative Methods for Solving Linear Systems 369
10.1 Convergence of Sequences of Vectors and Matrices . . . . . . . . . . . . . . 369
10.2 Convergence of Iterative Methods . . . . . . . . . . . . . . . . . . . . . . . . 372
10.3 Methods of Jacobi, Gauss–Seidel, and Relaxation . . . . . . . . . . . . . . . 374
10.4 Convergence of the Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
10.5 Convergence Methods for Tridiagonal Matrices . . . . . . . . . . . . . . . . 385
10.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
10.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
11 The Dual Space and Duality 395
11.1 The Dual Space E∗ and Linear Forms . . . . . . . . . . . . . . . . . . . . . 395
11.2 Pairing and Duality Between E and E∗ . . . . . . . . . . . . . . . . . . . . 402
11.3 The Duality Theorem and Some Consequences . . . . . . . . . . . . . . . . 407
11.4 The Bidual and Canonical Pairings . . . . . . . . . . . . . . . . . . . . . . . 413
11.5 Hyperplanes and Linear Forms . . . . . . . . . . . . . . . . . . . . . . . . . 415
11.6 Transpose of a Linear Map and of a Matrix . . . . . . . . . . . . . . . . . . 416
11.7 Properties of the Double Transpose . . . . . . . . . . . . . . . . . . . . . . . 423
11.8 The Four Fundamental Subspaces . . . . . . . . . . . . . . . . . . . . . . . 425
11.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
11.10 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429
12 Euclidean Spaces 433
12.1 Inner Products, Euclidean Spaces . . . . . . . . . . . . . . . . . . . . . . . . 433
12.2 Orthogonality and Duality in Euclidean Spaces . . . . . . . . . . . . . . . . 442
12.3 Adjoint of a Linear Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449
12.4 Existence and Construction of Orthonormal Bases . . . . . . . . . . . . . . 452
12.5 Linear Isometries (Orthogonal Transformations) . . . . . . . . . . . . . . . . 459
12.6 The Orthogonal Group, Orthogonal Matrices . . . . . . . . . . . . . . . . . 462
12.7 The Rodrigues Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464
12.8 QR-Decomposition for Invertible Matrices . . . . . . . . . . . . . . . . . . . 467
12.9 Some Applications of Euclidean Geometry . . . . . . . . . . . . . . . . . . . 472
12.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
12.11 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475
13 QR-Decomposition for Arbitrary Matrices 487
13.1 Orthogonal Reflections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487
13.2 QR-Decomposition Using Householder Matrices . . . . . . . . . . . . . . . . 492
13.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502
13.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502
14 Hermitian Spaces 509
14.1 Hermitian Spaces, Pre-Hilbert Spaces . . . . . . . . . . . . . . . . . . . . . 509
14.2 Orthogonality, Duality, Adjoint of a Linear Map . . . . . . . . . . . . . . . 518
14.3 Linear Isometries (Also Called Unitary Transformations) . . . . . . . . . . . 523
14.4 The Unitary Group, Unitary Matrices . . . . . . . . . . . . . . . . . . . . . 525
14.5 Hermitian Reflections and QR-Decomposition . . . . . . . . . . . . . . . . . 528
14.6 Orthogonal Projections and Involutions . . . . . . . . . . . . . . . . . . . . 533
14.7 Dual Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 536
14.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543
14.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544
15 Eigenvectors and Eigenvalues 549
15.1 Eigenvectors and Eigenvalues of a Linear Map . . . . . . . . . . . . . . . . . 549
15.2 Reduction to Upper Triangular Form . . . . . . . . . . . . . . . . . . . . . . 557
15.3 Location of Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 561
15.4 Conditioning of Eigenvalue Problems . . . . . . . . . . . . . . . . . . . . . . 565
15.5 Eigenvalues of the Matrix Exponential . . . . . . . . . . . . . . . . . . . . . 567
15.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 569
15.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 570
16 Unit Quaternions and Rotations in SO(3) 581
16.1 The Group SU(2) and the Skew Field H of Quaternions . . . . . . . . . . . 581
16.2 Representation of Rotation in SO(3) By Quaternions in SU(2) . . . . . . . 583
16.3 Matrix Representation of the Rotation rq . . . . . . . . . . . . . . . . . . . 588
16.4 An Algorithm to Find a Quaternion Representing a Rotation . . . . . . . . 590
16.5 The Exponential Map exp : su(2) → SU(2) . . . . . . . . . . . . . . . . . . 593
16.6 Quaternion Interpolation ~ . . . . . . . . . . . . . . . . . . . . . . . . . . . 595
16.7 Nonexistence of a “Nice” Section from SO(3) to SU(2) . . . . . . . . . . . . 597
16.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 599
16.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 600
17 Spectral Theorems 603
17.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 603
17.2 Normal Linear Maps: Eigenvalues and Eigenvectors . . . . . . . . . . . . . . 603
17.3 Spectral Theorem for Normal Linear Maps . . . . . . . . . . . . . . . . . . . 609
17.4 Self-Adjoint and Other Special Linear Maps . . . . . . . . . . . . . . . . . . 614
17.5 Normal and Other Special Matrices . . . . . . . . . . . . . . . . . . . . . . . 620
17.6 Rayleigh–Ritz Theorems and Eigenvalue Interlacing . . . . . . . . . . . . . 623
17.7 The Courant–Fischer Theorem; Perturbation Results . . . . . . . . . . . . . 628
17.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 631
17.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 632
18 Computing Eigenvalues and Eigenvectors 639
18.1 The Basic QR Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 641
18.2 Hessenberg Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 647
18.3 Making the QR Method More Efficient Using Shifts . . . . . . . . . . . . . 653
18.4 Krylov Subspaces; Arnoldi Iteration . . . . . . . . . . . . . . . . . . . . . . 658
18.5 GMRES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 662
18.6 The Hermitian Case; Lanczos Iteration . . . . . . . . . . . . . . . . . . . . . 663
18.7 Power Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664
18.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 666
18.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667
19 Introduction to The Finite Elements Method 669
19.1 A One-Dimensional Problem: Bending of a Beam . . . . . . . . . . . . . . . 669
19.2 A Two-Dimensional Problem: An Elastic Membrane . . . . . . . . . . . . . 680
19.3 Time-Dependent Boundary Problems . . . . . . . . . . . . . . . . . . . . . . 683
20 Graphs and Graph Laplacians; Basic Facts 691
20.1 Directed Graphs, Undirected Graphs, Weighted Graphs . . . . . . . . . . . 694
20.2 Laplacian Matrices of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 701
20.3 Normalized Laplacian Matrices of Graphs . . . . . . . . . . . . . . . . . . . 705
20.4 Graph Clustering Using Normalized Cuts . . . . . . . . . . . . . . . . . . . 709
20.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 711
20.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 712
21 Spectral Graph Drawing 715
21.1 Graph Drawing and Energy Minimization . . . . . . . . . . . . . . . . . . . 715
21.2 Examples of Graph Drawings . . . . . . . . . . . . . . . . . . . . . . . . . . 718
21.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 722
22 Singular Value Decomposition and Polar Form 725
22.1 Properties of f ∗ ◦ f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 725
22.2 Singular Value Decomposition for Square Matrices . . . . . . . . . . . . . . 731
22.3 Polar Form for Square Matrices . . . . . . . . . . . . . . . . . . . . . . . . . 735
22.4 Singular Value Decomposition for Rectangular Matrices . . . . . . . . . . . 737
22.5 Ky Fan Norms and Schatten Norms . . . . . . . . . . . . . . . . . . . . . . 741
22.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 742
22.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 742
23 Applications of SVD and Pseudo-Inverses 747
23.1 Least Squares Problems and the Pseudo-Inverse . . . . . . . . . . . . . . . . 747
23.2 Properties of the Pseudo-Inverse . . . . . . . . . . . . . . . . . . . . . . . . 754
23.3 Data Compression and SVD . . . . . . . . . . . . . . . . . . . . . . . . . . . 759
23.4 Principal Components Analysis (PCA) . . . . . . . . . . . . . . . . . . . . . 761
23.5 Best Affine Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . 772
23.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 776
23.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 777
II Affine and Projective Geometry 781
24 Basics of Affine Geometry 783
24.1 Affine Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 783
24.2 Examples of Affine Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . 792
24.3 Chasles’s Identity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 793
24.4 Affine Combinations, Barycenters . . . . . . . . . . . . . . . . . . . . . . . . 794
24.5 Affine Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 799
24.6 Affine Independence and Affine Frames . . . . . . . . . . . . . . . . . . . . . 805
24.7 Affine Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 811
24.8 Affine Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 818
24.9 Affine Geometry: A Glimpse . . . . . . . . . . . . . . . . . . . . . . . . . . 820
24.10 Affine Hyperplanes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 824
24.11 Intersection of Affine Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 826
25 Embedding an Affine Space in a Vector Space 829
25.1 The “Hat Construction,” or Homogenizing . . . . . . . . . . . . . . . . . . . 829
25.2 Affine Frames of E and Bases of ˆE . . . . . . . . . . . . . . . . . . . . . . . 836
25.3 Another Construction of ˆE . . . . . . . . . . . . . . . . . . . . . . . . . . . 839
25.4 Extending Affine Maps to Linear Maps . . . . . . . . . . . . . . . . . . . . . 842
26 Basics of Projective Geometry 847
26.1 Why Projective Spaces? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 847
26.2 Projective Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 852
26.3 Projective Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 857
26.4 Projective Frames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 860
26.5 Projective Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 874
26.6 Finding a Homography Between Two Projective Frames . . . . . . . . . . . 880
26.7 Affine Patches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 893
26.8 Projective Completion of an Affine Space . . . . . . . . . . . . . . . . . . . 896
26.9 Making Good Use of Hyperplanes at Infinity . . . . . . . . . . . . . . . . . 901
26.10 The Cross-Ratio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 904
26.11 Fixed Points of Homographies and Homologies . . . . . . . . . . . . . . . . 908
26.12 Duality in Projective Geometry . . . . . . . . . . . . . . . . . . . . . . . . . 922
26.13 Cross-Ratios of Hyperplanes . . . . . . . . . . . . . . . . . . . . . . . . . . . 926
26.14 Complexification of a Real Projective Space . . . . . . . . . . . . . . . . . . 928
26.15 Similarity Structures on a Projective Space . . . . . . . . . . . . . . . . . . 930
26.16 Some Applications of Projective Geometry . . . . . . . . . . . . . . . . . . . 939
III The Geometry of Bilinear Forms 945
27 The Cartan–Dieudonn ́e Theorem 947
27.1 The Cartan–Dieudonn ́e Theorem for Linear Isometries . . . . . . . . . . . . 947
27.2 Affine Isometries (Rigid Motions) . . . . . . . . . . . . . . . . . . . . . . . . 959
27.3 Fixed Points of Affine Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . 961
27.4 Affine Isometries and Fixed Points . . . . . . . . . . . . . . . . . . . . . . . 963
27.5 The Cartan–Dieudonn ́e Theorem for Affine Isometries . . . . . . . . . . . . 969
28 Isometries of Hermitian Spaces 973
28.1 The Cartan–Dieudonn ́e Theorem, Hermitian Case . . . . . . . . . . . . . . . 973
28.2 Affine Isometries (Rigid Motions) . . . . . . . . . . . . . . . . . . . . . . . . 982
29 The Geometry of Bilinear Forms; Witt’s Theorem 987
29.1 Bilinear Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 987
29.2 Sesquilinear Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 995
29.3 Orthogonality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 999
29.4 Adjoint of a Linear Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1004
29.5 Isometries Associated with Sesquilinear Forms . . . . . . . . . . . . . . . . . 1006
29.6 Totally Isotropic Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 1010
29.7 Witt Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1016
29.8 Symplectic Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1024
29.9 Orthogonal Groups and the Cartan–Dieudonn ́e Theorem . . . . . . . . . . . 1028
29.10 Witt’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1035
IV Algebra: PID’s, UFD’s, Noetherian Rings, Tensors, Modules over a PID, Normal Forms 1041
30 Polynomials, Ideals and PID’s 1043
30.1 Multisets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1043
30.2 Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1044
30.3 Euclidean Division of Polynomials . . . . . . . . . . . . . . . . . . . . . . . 1050
30.4 Ideals, PID’s, and Greatest Common Divisors . . . . . . . . . . . . . . . . . 1052
30.5 Factorization and Irreducible Factors in KX . . . . . . . . . . . . . . . . . 1060 30.6 Roots of Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1064
30.7 Polynomial Interpolation (Lagrange, Newton, Hermite) . . . . . . . . . . . . 1071
31 Annihilating Polynomials; Primary Decomposition 1079
31.1 Annihilating Polynomials and the Minimal Polynomial . . . . . . . . . . . . 1081
31.2 Minimal Polynomials of Diagonalizable Linear Maps . . . . . . . . . . . . . 1083
31.3 Commuting Families of Linear Maps . . . . . . . . . . . . . . . . . . . . . . 1086
31.4 The Primary Decomposition Theorem . . . . . . . . . . . . . . . . . . . . . 1089
31.5 Jordan Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1095
31.6 Nilpotent Linear Maps and Jordan Form . . . . . . . . . . . . . . . . . . . . 1098
31.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1104
31.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1105
32 UFD’s, Noetherian Rings, Hilbert’s Basis Theorem 1109
32.1 Unique Factorization Domains (Factorial Rings) . . . . . . . . . . . . . . . . 1109
32.2 The Chinese Remainder Theorem . . . . . . . . . . . . . . . . . . . . . . . . 1123
32.3 Noetherian Rings and Hilbert’s Basis Theorem . . . . . . . . . . . . . . . . 1129
32.4 Futher Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1133
33 Tensor Algebras 1135
33.1 Linear Algebra Preliminaries: Dual Spaces and Pairings . . . . . . . . . . . 1137
33.2 Tensors Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1142
33.3 Bases of Tensor Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1154
33.4 Some Useful Isomorphisms for Tensor Products . . . . . . . . . . . . . . . . 1155
33.5 Duality for Tensor Products . . . . . . . . . . . . . . . . . . . . . . . . . . . 1159
33.6 Tensor Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1165
33.7 Symmetric Tensor Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1172
33.8 Bases of Symmetric Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . 1176
33.9 Some Useful Isomorphisms for Symmetric Powers . . . . . . . . . . . . . . . 1179
33.10 Duality for Symmetric Powers . . . . . . . . . . . . . . . . . . . . . . . . . . 1179
33.11 Symmetric Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1183
33.12 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1186
34 Exterior Tensor Powers and Exterior Algebras 1189
34.1 Exterior Tensor Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1189
34.2 Bases of Exterior Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1194
34.3 Some Useful Isomorphisms for Exterior Powers . . . . . . . . . . . . . . . . 1197
34.4 Duality for Exterior Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . 1197
34.5 Exterior Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1201
34.6 The Hodge ∗-Operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1205
34.7 Left and Right Hooks ~ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1209
34.8 Testing Decomposability ~ . . . . . . . . . . . . . . . . . . . . . . . . . . . 1219
34.9 The Grassmann-Pl ̈ucker’s Equations and Grassmannians ~ . . . . . . . . . 1222
34.10 Vector-Valued Alternating Forms . . . . . . . . . . . . . . . . . . . . . . . . 1225
34.11 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1229
35 Introduction to Modules; Modules over a PID 1231
35.1 Modules over a Commutative Ring . . . . . . . . . . . . . . . . . . . . . . . 1231
35.2 Finite Presentations of Modules . . . . . . . . . . . . . . . . . . . . . . . . . 1240
35.3 Tensor Products of Modules over a Commutative Ring . . . . . . . . . . . . 1246
35.4 Torsion Modules over a PID; Primary Decomposition . . . . . . . . . . . . . 1249
35.5 Finitely Generated Modules over a PID . . . . . . . . . . . . . . . . . . . . 1255
35.6 Extension of the Ring of Scalars . . . . . . . . . . . . . . . . . . . . . . . . 1271
36 Normal Forms; The Rational Canonical Form 1277
36.1 The Torsion Module Associated With An Endomorphism . . . . . . . . . . 1277
36.2 The Rational Canonical Form . . . . . . . . . . . . . . . . . . . . . . . . . . 1285
36.3 The Rational Canonical Form, Second Version . . . . . . . . . . . . . . . . . 1292
36.4 The Jordan Form Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . 1293
36.5 The Smith Normal Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1296
V Topology, Differential Calculus 1309
37 Topology 1311
37.1 Metric Spaces and Normed Vector Spaces . . . . . . . . . . . . . . . . . . . 1311
37.2 Topological Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1318
37.3 Continuous Functions, Limits . . . . . . . . . . . . . . . . . . . . . . . . . . 1327
37.4 Connected Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1335
37.5 Compact Sets and Locally Compact Spaces . . . . . . . . . . . . . . . . . . 1344
37.6 Second-Countable and Separable Spaces . . . . . . . . . . . . . . . . . . . . 1355
37.7 Sequential Compactness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1359
37.8 Complete Metric Spaces and Compactness . . . . . . . . . . . . . . . . . . . 1365
37.9 Completion of a Metric Space . . . . . . . . . . . . . . . . . . . . . . . . . . 1368
37.10 The Contraction Mapping Theorem . . . . . . . . . . . . . . . . . . . . . . 1375
37.11 Continuous Linear and Multilinear Maps . . . . . . . . . . . . . . . . . . . . 1379
37.12 Completion of a Normed Vector Space . . . . . . . . . . . . . . . . . . . . . 1386
37.13 Normed Affine Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1389
37.14 Futher Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1389
38 A Detour On Fractals 1391
38.1 Iterated Function Systems and Fractals . . . . . . . . . . . . . . . . . . . . 1391
39 Differential Calculus 1399
39.1 Directional Derivatives, Total Derivatives . . . . . . . . . . . . . . . . . . . 1399
39.2 Properties of Derivatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1408
39.3 Jacobian Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1413
39.4 The Implicit and The Inverse Function Theorems . . . . . . . . . . . . . . . 1421
39.5 Tangent Spaces and Differentials . . . . . . . . . . . . . . . . . . . . . . . . 1428
39.6 Second-Order and Higher-Order Derivatives . . . . . . . . . . . . . . . . . . 1430
39.7 Taylor’s formula, Fa`a di Bruno’s formula . . . . . . . . . . . . . . . . . . . . 1436
39.8 Vector Fields, Covariant Derivatives, Lie Brackets . . . . . . . . . . . . . . . 1441
39.9 Futher Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1443
39.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1443
39.11 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1444
VI Preliminaries for Optimization Theory 1447
40 Extrema of Real-Valued Functions 1449
40.1 Local Extrema and Lagrange Multipliers . . . . . . . . . . . . . . . . . . . . 1450
40.2 Using Second Derivatives to Find Extrema . . . . . . . . . . . . . . . . . . . 1462
40.3 Using Convexity to Find Extrema . . . . . . . . . . . . . . . . . . . . . . . 1465
40.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1475
40.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1476
41 Newton’s Method and Its Generalizations 1479
41.1 Newton’s Method for Real Functions of a Real Argument . . . . . . . . . . 1479
41.2 Generalizations of Newton’s Method . . . . . . . . . . . . . . . . . . . . . . 1481
41.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1490
41.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1490
42 Quadratic Optimization Problems 1499
42.1 Quadratic Optimization: The Positive Definite Case . . . . . . . . . . . . . 1499
42.2 Quadratic Optimization: The General Case . . . . . . . . . . . . . . . . . . 1509
42.3 Maximizing a Quadratic Function on the Unit Sphere . . . . . . . . . . . . 1514
42.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1519
42.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1520
43 Schur Complements and Applications 1521
43.1 Schur Complements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1521
43.2 SPD Matrices and Schur Complements . . . . . . . . . . . . . . . . . . . . . 1524
43.3 SP Semidefinite Matrices and Schur Complements . . . . . . . . . . . . . . 1525
43.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1527
43.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1527
VII Linear Optimization 1529
44 Convex Sets, Cones, H-Polyhedra 1531
44.1 What is Linear Programming? . . . . . . . . . . . . . . . . . . . . . . . . . 1531
44.2 Affine Subsets, Convex Sets, Hyperplanes, Half-Spaces . . . . . . . . . . . . 1533
44.3 Cones, Polyhedral Cones, and H-Polyhedra . . . . . . . . . . . . . . . . . . 1536
44.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1541
44.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1542
45 Linear Programs 1543
45.1 Linear Programs, Feasible Solutions, Optimal Solutions . . . . . . . . . . . 1543
45.2 Basic Feasible Solutions and Vertices . . . . . . . . . . . . . . . . . . . . . . 1550
45.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1557
45.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1557
46 The Simplex Algorithm 1561
46.1 The Idea Behind the Simplex Algorithm . . . . . . . . . . . . . . . . . . . . 1561
46.2 The Simplex Algorithm in General . . . . . . . . . . . . . . . . . . . . . . . 1570
46.3 How to Perform a Pivoting Step Efficiently . . . . . . . . . . . . . . . . . . 1577
46.4 The Simplex Algorithm Using Tableaux . . . . . . . . . . . . . . . . . . . . 1581
46.5 Computational Efficiency of the Simplex Method . . . . . . . . . . . . . . . 1590
46.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1591
46.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1591
47 Linear Programming and Duality 1595
47.1 Variants of the Farkas Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . 1595
47.2 The Duality Theorem in Linear Programming . . . . . . . . . . . . . . . . . 1601
47.3 Complementary Slackness Conditions . . . . . . . . . . . . . . . . . . . . . 1609
47.4 Duality for Linear Programs in Standard Form . . . . . . . . . . . . . . . . 1610
47.5 The Dual Simplex Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 1613
47.6 The Primal-Dual Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 1620
47.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1630
47.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1630
VIII NonLinear Optimization 1635
48 Basics of Hilbert Spaces 1637
48.1 The Projection Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1637
48.2 Duality and the Riesz Representation Theorem . . . . . . . . . . . . . . . . 1650
48.3 Farkas–Minkowski Lemma in Hilbert Spaces . . . . . . . . . . . . . . . . . . 1655
48.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1656
48.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1657
49 General Results of Optimization Theory 1659
49.1 Optimization Problems; Basic Terminology . . . . . . . . . . . . . . . . . . 1659
49.2 Existence of Solutions of an Optimization Problem . . . . . . . . . . . . . . 1663
49.3 Minima of Quadratic Functionals . . . . . . . . . . . . . . . . . . . . . . . . 1667
49.4 Elliptic Functionals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1674
49.5 Iterative Methods for Unconstrained Problems . . . . . . . . . . . . . . . . 1677
49.6 Gradient Descent Methods for Unconstrained Problems . . . . . . . . . . . 1680
49.7 Convergence of Gradient Descent with Variable Stepsize . . . . . . . . . . . 1687
49.8 Steepest Descent for an Arbitrary Norm . . . . . . . . . . . . . . . . . . . . 1691
49.9 Newton’s Method For Finding a Minimum . . . . . . . . . . . . . . . . . . . 1693
49.10 Conjugate Gradient Methods; Unconstrained Problems . . . . . . . . . . . . 1697
49.11 Gradient Projection for Constrained Optimization . . . . . . . . . . . . . . 1708
49.12 Penalty Methods for Constrained Optimization . . . . . . . . . . . . . . . . 1711
49.13 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1713
49.14 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1714
50 Introduction to Nonlinear Optimization 1719
50.1 The Cone of Feasible Directions . . . . . . . . . . . . . . . . . . . . . . . . . 1721
50.2 Active Constraints and Qualified Constraints . . . . . . . . . . . . . . . . . 1727
50.3 The Karush–Kuhn–Tucker Conditions . . . . . . . . . . . . . . . . . . . . . 1734
50.4 Equality Constrained Minimization . . . . . . . . . . . . . . . . . . . . . . . 1745
50.5 Hard Margin Support Vector Machine; Version I . . . . . . . . . . . . . . . 1750
50.6 Hard Margin Support Vector Machine; Version II . . . . . . . . . . . . . . . 1755
50.7 Lagrangian Duality and Saddle Points . . . . . . . . . . . . . . . . . . . . . 1763
50.8 Weak and Strong Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1772
50.9 Handling Equality Constraints Explicitly . . . . . . . . . . . . . . . . . . . . 1780
50.10 Dual of the Hard Margin Support Vector Machine . . . . . . . . . . . . . . 1783
50.11 Conjugate Function and Legendre Dual Function . . . . . . . . . . . . . . . 1788
50.12 Some Techniques to Obtain a More Useful Dual Program . . . . . . . . . . 1798
50.13 Uzawa’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1802
50.14 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1808
50.15 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1809
51 Subgradients and Subdifferentials ~ 1811
51.1 Extended Real-Valued Convex Functions . . . . . . . . . . . . . . . . . . . . 1813
51.2 Subgradients and Subdifferentials . . . . . . . . . . . . . . . . . . . . . . . . 1822
51.3 Basic Properties of Subgradients and Subdifferentials . . . . . . . . . . . . . 1834
51.4 Additional Properties of Subdifferentials . . . . . . . . . . . . . . . . . . . . 1840
51.5 The Minimum of a Proper Convex Function . . . . . . . . . . . . . . . . . . 1844
51.6 Generalization of the Lagrangian Framework . . . . . . . . . . . . . . . . . 1851
51.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1854
51.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1856
52 Dual Ascent Methods; ADMM 1857
52.1 Dual Ascent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1859
52.2 Augmented Lagrangians and the Method of Multipliers . . . . . . . . . . . . 1863
52.3 ADMM: Alternating Direction Method of Multipliers . . . . . . . . . . . . . 1868
52.4 Convergence of ADMM ~ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1871
52.5 Stopping Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1880
52.6 Some Applications of ADMM . . . . . . . . . . . . . . . . . . . . . . . . . . 1881
52.7 Solving Hard Margin (SVMh2) Using ADMM . . . . . . . . . . . . . . . . . 1886
52.8 Applications of ADMM to `1-Norm Problems . . . . . . . . . . . . . . . . . 1888
52.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1893
52.10 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1894
IX Applications to Machine Learning 1897
53 Positive Definite Kernels 1899
53.1 Feature Maps and Kernel Functions . . . . . . . . . . . . . . . . . . . . . . 1899
53.2 Basic Properties of Positive Definite Kernels . . . . . . . . . . . . . . . . . . 1906
53.3 Hilbert Space Representation of a Positive Kernel . . . . . . . . . . . . . . . 1912
53.4 Kernel PCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1915
53.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1918
53.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1919
54 Soft Margin Support Vector Machines 1921
54.1 Soft Margin Support Vector Machines; (SVMs1) . . . . . . . . . . . . . . . . 1924
54.2 Solving SVM (SVMs1) Using ADMM . . . . . . . . . . . . . . . . . . . . . . 1939
54.3 Soft Margin Support Vector Machines; (SVMs2) . . . . . . . . . . . . . . . . 1940
54.4 Solving SVM (SVMs2) Using ADMM . . . . . . . . . . . . . . . . . . . . . . 1947
54.5 Soft Margin Support Vector Machines; (SVMs2′ ) . . . . . . . . . . . . . . . 1948
54.6 Classification of the Data Points in Terms of ν (SVMs2′ ) . . . . . . . . . . . 1958
54.7 Existence of Support Vectors for (SVMs2′ ) . . . . . . . . . . . . . . . . . . . 1961
54.8 Solving SVM (SVMs2′ ) Using ADMM . . . . . . . . . . . . . . . . . . . . . 1972
54.9 Soft Margin Support Vector Machines; (SVMs3) . . . . . . . . . . . . . . . . 1976
54.10 Classification of the Data Points in Terms of ν (SVMs3) . . . . . . . . . . . 1983
54.11 Existence of Support Vectors for (SVMs3) . . . . . . . . . . . . . . . . . . . 1985
54.12 Solving SVM (SVMs3) Using ADMM . . . . . . . . . . . . . . . . . . . . . . 1987
54.13 Soft Margin SVM; (SVMs4) . . . . . . . . . . . . . . . . . . . . . . . . . . . 1990
54.14 Solving SVM (SVMs4) Using ADMM . . . . . . . . . . . . . . . . . . . . . . 1999
54.15 Soft Margin SVM; (SVMs5) . . . . . . . . . . . . . . . . . . . . . . . . . . . 2001
54.16 Solving SVM (SVMs5) Using ADMM . . . . . . . . . . . . . . . . . . . . . . 2005
54.17 Summary and Comparison of the SVM Methods . . . . . . . . . . . . . . . 2007
54.18 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2020
55 Ridge Regression, Lasso, Elastic Net 2025
55.1 Ridge Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2026
55.2 Ridge Regression; Learning an Affine Function . . . . . . . . . . . . . . . . 2029
55.3 Kernel Ridge Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2038
55.4 Lasso Regression (`1-Regularized Regression) . . . . . . . . . . . . . . . . . 2042
55.5 Lasso Regression; Learning an Affine Function . . . . . . . . . . . . . . . . . 2046
55.6 Elastic Net Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2052
55.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2058
55.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2058
56 ν-SV Regression 2061
56.1 ν-SV Regression; Derivation of the Dual . . . . . . . . . . . . . . . . . . . . 2061
56.2 Existence of Support Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . 2072
56.3 Solving ν-Regression Using ADMM . . . . . . . . . . . . . . . . . . . . . . . 2082
56.4 Kernel ν-SV Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2088
56.5 ν-Regression Version 2; Penalizing b . . . . . . . . . . . . . . . . . . . . . . 2091
56.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2098
56.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2099
X Appendices 2101
A Total Orthogonal Families in Hilbert Spaces 2103
A.1 Total Orthogonal Families, Fourier Coefficients . . . . . . . . . . . . . . . . 2103
A.2 The Hilbert Space `2(K) and the Riesz–Fischer Theorem . . . . . . . . . . . 2112
A.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2121
A.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2122
B Matlab Programs 2123
B.1 Hard Margin (SVMh2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2123
B.2 Soft Margin SVM (SVMs2′ ) . . . . . . . . . . . . . . . . . . . . . . . . . . . 2127
B.3 Soft Margin SVM (SVMs3) . . . . . . . . . . . . . . . . . . . . . . . . . . . 2135
B.4 ν-SV Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2140
C Zorn’s Lemma; Some Applications 2147
C.1 Statement of Zorn’s Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . 2147
C.2 Proof of the Existence of a Basis in a Vector Space . . . . . . . . . . . . . . 2148
C.3 Existence of Maximal Proper Ideals . . . . . . . . . . . . . . . . . . . . . . 2149
Bibliography 2151
Index 2163